#!/usr/bin/env python
# encoding: utf-8
'''
@author: Excelsiorly
@license: (C) Copyright 2022, All Rights Reserved.
@contact: excelsiorly@qq.com
@file: 160. 相交链表.py
@time: 2022/1/7 13:58
@desc: https://leetcode-cn.com/problems/intersection-of-two-linked-lists/
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
@解题思路：
    1. 哈希集合、遍历, Ot(m+n), Os(m)
    2. 单纯的用列表会超时
'''
# Definition for singly-linked list.
class ListNode(object):
    def __init__(self, x):
        self.val = x
        self.next = None

class Solution(object):
    def getIntersectionNode(self, headA, headB):
        """
        :type head1, head1: ListNode
        :rtype: ListNode
        """
        if not (headA and headB): return None
        list = set() # 用list会超时
        p = headA
        while p:
            list.add(p)
            p = p.next
        q = headB
        while q:
            if q in list:
                return q
            else:
                q = q.next
        return None